package demo.practice.niuke.zs;

//import com.sun.tools.javac.Main;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class CD101 {

    public static int[][] getNearLessNoRepeat(int[] arr) {

        if(arr==null)
            return null;
        int [][] tg= new int[arr.length][2];

        Stack<Integer> stack= new Stack<>();

        //单调递增栈。arr=[3 4 1 5 6 2 7]    最近，且值比当前 i位置值小的。
        //3---5
        //1---4
        //0---3
        for(int i=0;i<arr.length;i++){
            if(stack.isEmpty()|| arr[stack.peek()]< arr[i]){
                stack.add(i);
            }else{
                while (! stack.isEmpty() && arr[stack.peek()]>= arr[i]){
                    Integer pop = stack.pop();
                    tg[pop][0]=stack.size()==0? -1: stack.peek();
                }
                stack.add(i);
            }
        }

        while (! stack.isEmpty() ){
            Integer pop = stack.pop();
            tg[pop][0]=stack.size()==0? -1: stack.peek();
        }

        for(int i=arr.length-1;i>=0;i--){
            if(stack.isEmpty()|| arr[stack.peek()]< arr[i]){
                stack.add(i);
            }else{
                while (! stack.isEmpty()&& arr[stack.peek()]>= arr[i] ){
                    Integer pop = stack.pop();
                    tg[pop][1]=stack.size()==0? -1: stack.peek();
                }
                stack.add(i);
            }
        }

        while (! stack.isEmpty() ){
            Integer pop = stack.pop();
            tg[pop][1]=stack.size()==0? -1: stack.peek();
        }



        return tg;
    }




    public static void main(String[] args) {

//        CD101 cd101= new CD101();
        int[][] nearLessNoRepeat = getNearLessNoRepeat(new int[]{3, 4, 1, 5, 6, 2, 7});
        for (int[] a: nearLessNoRepeat
             ) {
            System.out.println(Arrays.toString(a));
        }



       /* Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] data = new int[n];
            for (int i = 0; i < data.length; i++) {
                data[i] = sc.nextInt();
            }
            int[][] result = getNearLessNoRepeat(data);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < result.length; i++) {
                sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n');
            }
            System.out.print(sb);
        }*/
    }
}
